In recent years in has become increasingly common to utilise vector graphics in computer graphics. As is known, in the art, one key advantage of vector graphics over raster graphics is the ability to provide resolution-independent images, i.e. images that can essentially be scaled indefinitely without degrading. For example, the individual characterisers in computer fonts, such as TrueType™, are typically stored as vector images.
Vector graphics are based on the use of individually defined geometrical objects, and are typically described by one or more line segments, e.g. straight lines or curves (such as quadratic (bezier) curves, elliptical arcs, cubic (bezier) curves) that are connected together at anchor points to form a path.
Vector graphics objects/paths are defined and manipulated in a space, commonly known as “user space”. In order to output the vector graphics, objects/paths to a video display or printer, however, the objects/paths as defined in user space need to be converted into a suitable form so as to be displayed on a screen or to be outputted on a printer. This conversion typically involves projecting the objects/paths as defined in user space to another space, commonly referred to as “surface space”, that corresponds to the perspective (geometry) of the output (e.g., screen or printer) on which the objects/paths are to be viewed. The transformation between user space and surface space is typically referred to as the “user-to-surface transformation”.
Once the vector graphics objects/paths have been converted into surface space representations, they are then rendered.
This process, as is known in the art, typically involves generating one or more graphics primitives, such as triangles, that cover the surface space representations of the objects/paths and rasterising the primitives to a plurality of sampling points within the primitives which are then sampled to determine whether each sampling point falls within the projected objects/paths or not. Based on this determination, the plurality of sampling points are assigned data, such as red, green and blue (RGB) colour values and an “alpha” transparency value, as appropriate to allow the objects/paths to be correctly displayed. These processes are commonly referred to as rasterising and shading, respectively.
(In 3D graphics literature, the term “rasterisation” is sometimes used to mean both object conversion to sample positions and shading. However, herein, rasterisation will be used to refer to converting object data to sampling point addresses only.)
These processes are typically carried out, as is known in the art, by representing the sampling points using discrete graphical entities usually referred to as “fragments” on which the graphics processing operations (such as shading) are carried out. Thus, the fragments are, in effect, the graphics entities that are processed by the graphics processing system (that pass through the graphics pipeline).
Each fragment can reasonably be thought of as being effectively equivalent to a “pixel” of the scene being processed. Each fragment may correspond to a single or to a plurality of sampling points. Each fragment may correspond to a single pixel (picture element) in the final display (output) (since as the pixels are the singularities in the final display, there may be a one-to-one mapping between the fragments the graphics processor operates on and the pixels of the display). More typically, however, it will be the case that there is not a one-to-one correspondence between a fragment and a display pixel, for example where particular forms of post-processing, such as down-scaling, are carried out on the rendered image prior to displaying the final image.
Two types of objects that are commonly found in vector graphics are “filled” objects and stroked objects. The process of filling involves applying a single block of colour, gradient, pattern or image to the area within an object or closed path. The process of stroking meanwhile can be thought of effectively as adding a width to the path by dragging a line-shaped pen tip of a particular width along the path. More specifically, the centre point of the pen-tip follows the path, and the tip is orientated so as to always be perpendicular to the path. Equivalently, therefore, the boundary of a stroked path can also be defined by the set of points from which a line of length (at most) w/2 (for a stroked path of width w), and which is perpendicular to the path, can be drawn to a point on the path.
The rendering of stroked paths, and of stroked curves in particular, is traditionally an expensive operation in terms of load on the CPU. Furthermore, the rendering of stroked curves can often be complicated in that in certain situations a first section of a stroked curve can overlap a second section of the stroked curve. This situation is commonly known in the art as “self-overlap”, and occurs when the radius of curvature of the centre curve is smaller than half the stroke width.
One common method of rendering a stroked curve is to subdivide the curve into a plurality of individual lines or filled paths on the CPU, which can then each be rendered separately. Another method that is often used for rendering stroked curves is to use dedicated curve rendering hardware.
The Applicants believe, however, that there is scope for further, and improved, techniques for rendering stroked paths, and in particular stroked curves.